'''
哈希表:一个通过哈希函数来计算数据存储位置的数据结构,通常支持如下操作:
    insert(key,value):插入键值对(key,value)
    get(key):如果存在键为key的键值对则返回其value,否则返回空值
    delete(key):删除键为key的键值对
'''
'''
直接寻址表
    当关键字的全域U比较小时,直接寻址是一种简单而有效的方法
    直接寻址表的技术缺点:
        当域U很大时,需要消耗大量内存,很不实际
        如果域U很大而实际出现的key很少,则大量空间被浪费
        无法处理关键字不是数字的情况
'''
'''
哈希
    直接寻址表:key为k的元素放到k位置上
    改进直接寻址表:哈希(Hashing)
        构建大小为m的寻址表T
        key为k的元素放到h(k)位置上
        h(k)是一个函数,其将域U映射到表T[0,1,...,m-1]
'''
'''
哈希表
    哈希表(Hash Table,又称为散列表),是一种线性表的存储结构.哈希表由一个直接寻址表和一个哈希函数
    组成.哈希函数h(k)将元素关键字k作为自变量,返回元素的存储下标
    假设有一个长度为7的哈希表,哈希函数h(k) = k%7.元素集合{14,22,3,5}的存储方式如下图
    k    = 14  22  ()  3  ()  5  ()
    h(k) = 0   1   2   3  4   5  6   哈希函数的取值只有0-6
哈希冲突
    由于哈希表的大小是有限的,而要存储的值的总数量是无限的,因此对于任何哈希函数,都会出现两个不同元素映射到同一个位置上的情况,
    这种情况叫做哈希冲突
    比如h(k) = k%7   h(0) = h(7) = h(14) = ...
解决哈希冲突--开放寻址法
开放寻址法:如果哈希函数返回的位置已经有值,则可以向后探查新的位置来存储这个值
    线性探查:如果位置i被占用,则探查i+1,i+2,....
    二次探查:如果位置i被占用,则探查i+1**2,i-1**2,i+2**2,i-2**2,......
    二度哈希:有n个哈希函数,当使用第一个哈希函数h1发生冲突时,则尝试使用h2,h3......
'''
'''
解决哈希冲突--拉链法
拉链法:哈希表每个位置都连接一个链表,当冲突发生时,冲突的元素将被加到该位置链表的最后
'''
'''
哈希表--常见哈希函数
除法哈希法: h(k) = k % m
乘法哈希法: h(k) = floor(m*(A*key%1))
全域哈希法: h(a,b)(k) = ((a*key + b) mod p) mod m  a,b = 1,2,3...,p-1
'''

class LinkList:
    # 内部类：链表节点
    class Node:
        def __init__(self, item=None):
            self.item = item  # 节点存储的数据
            self.next = None  # 指向下一个节点的指针（默认为空）

    # 内部类：链表迭代器
    class LinkListIterator:
        def __init__(self, node):
            self.node = node  # 初始化迭代器指向的起始节点

        def __next__(self):
            if self.node:  # 如果当前节点存在
                cur_node = self.node  # 保存当前节点
                self.node = cur_node.next  # 移动指针到下一个节点
                return cur_node.item  # 返回当前节点的数据
            else:
                raise StopIteration  # 节点不存在时停止迭代

        def __iter__(self):
            return self  # 返回迭代器自身

    # 链表初始化 ----------------------------------------
    def __init__(self, iterable=None):
        self.head = None  # 链表头指针
        self.tail = None  # 链表尾指针
        if iterable:
            self.extend(iterable)  # 如果提供可迭代对象，批量添加元素

    # 添加单个元素 --------------------------------------
    def append(self, obj):
        s = LinkList.Node(obj)  # 创建新节点

        if not self.head:  # 空链表情况
            self.head = s  # 头指针指向新节点
            self.tail = s  # 尾指针指向新节点
        else:  # 非空链表
            self.tail.next = s  # 当前尾节点的next指向新节点
            self.tail = s  # 更新尾指针为新节点

    # 批量添加元素 --------------------------------------
    def extend(self, iterable):
        for obj in iterable:  # 遍历可迭代对象
            self.append(obj)  # 调用append逐个添加

    # 查找元素 -----------------------------------------
    def find(self, obj):
        for n in self:  # 利用__iter__遍历链表
            if n == obj:  # 找到目标元素
                return True
        return False  # 遍历结束未找到

    # 迭代器支持 ---------------------------------------
    def __iter__(self):
        return self.LinkListIterator(self.head)  # 从head开始迭代

    # 链表可视化 ---------------------------------------
    def __repr__(self):
        return '<<' + ','.join(map(str, self)) + '>>'
        # 1. self触发__iter__迭代
        # 2. map将每个元素转为字符串
        # 3. 用逗号连接所有元素
        # 4. 添加<<>>装饰
class HashTable:
    def __init__(self,size=101):
        self.size = size
        self.T=[LinkList() for i in range(self.size)]

    def h(self,k):
        return k % self.size

    def insert(self,k):
        i = self.h(k)
        if self.find(k):
            print('重复的插入')
        else:
            self.T[i].append(k)

    def find(self,k):
        i = self.h(k)
        return self.T[i].find(k)